﻿// 2001. 可互换矩形的组数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;
/*
https://leetcode.cn/problems/number-of-pairs-of-interchangeable-rectangles/description/

用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。

如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。更规范的说法是，两个矩形满足 widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。

计算并返回 rectangles 中有多少对 可互换 矩形。



示例 1：

输入：rectangles = [[4,8],[3,6],[10,20],[15,30]]
输出：6
解释：下面按下标（从 0 开始）列出可互换矩形的配对情况：
- 矩形 0 和矩形 1 ：4/8 == 3/6
- 矩形 0 和矩形 2 ：4/8 == 10/20
- 矩形 0 和矩形 3 ：4/8 == 15/30
- 矩形 1 和矩形 2 ：3/6 == 10/20
- 矩形 1 和矩形 3 ：3/6 == 15/30
- 矩形 2 和矩形 3 ：10/20 == 15/30
示例 2：

输入：rectangles = [[4,5],[7,8]]
输出：0
解释：不存在成对的可互换矩形。


提示：

n == rectangles.length
1 <= n <= 105
rectangles[i].length == 2
1 <= widthi, heighti <= 105
*/


class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    long long interchangeableRectangles(vector<vector<int>>& rectangles) {
        long long ans = 0;
        unordered_map<long long, long long>  mm;
        for (int i = 0; i < rectangles.size(); i++) {
            int a = rectangles[i][0]; int b = rectangles[i][1];
            int gcdv = gcd(a, b);
            while (gcdv != 1) {
                a = a / gcdv; b = b / gcdv;
                gcdv = gcd(a, b);
            }
            rectangles[i][0] = a; rectangles[i][1] = b;
            long long hashv = 1LL * a * 1000000 + b;
            if (mm.count(hashv) != 0) {
                ans += mm[hashv];
            }
            mm[hashv]++;
        }

        return ans;
    }
};

int main()
{
    std::cout << "Hello World!\n";
}

 